package org.leetcode.middle.leetcode437;

import org.leetcode.TreeNode;

public class Solution {

    int count = 0;

    public int pathSum2(TreeNode root, int targetSum) {

        if (root==null){
            return count;
        }

        dfs2(root,0,targetSum);

        pathSum2(root.left,targetSum);
        pathSum2(root.right,targetSum);

        return count;
    }

    private void dfs2(TreeNode root,int pathSum,long targetSum){
        if (root==null){
            return;
        }

        if (pathSum+root.val==targetSum){
            count++;
        }

        dfs2(root.left,pathSum+root.val,targetSum);
        dfs2(root.right,pathSum+root.val,targetSum);
    }
    public int pathSum(TreeNode root, int targetSum) {
        if (root == null) {
            return 0;
        }

        dfs(root,targetSum);
        pathSum(root.left,targetSum);
        pathSum(root.right,targetSum);

        //使用pathSum来递归而不是dfs递归的原因：使用dfs递归会遗漏每个子节点作为新的起点来进行全新的路径搜索
//        dfs(root.left,targetSum);
//        dfs(root.right,targetSum);

        return count;
    }

    private void dfs(TreeNode root ,long targetSum){

        if (root==null){
            return;
        }

        if (root.val==targetSum){
            count++;
        }

        dfs(root.left,targetSum-root.val);
        dfs(root.right,targetSum-root.val);

    }
}
